package leet78subset

// 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
// 说明：解集不能包含重复的子集。
// 示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   []

func Subset(nums []int) [][]int {
	// 问题抽象为：从指定子集中挑选一个元素出来参与到组合中即可
	// 比如针对自己 [1,2,3] 我们挑选1出来，然后在剩余的自己 [2,3] 中我们继续重复刚才的操作，挑选2或者3出来，每一次挑选出来就写入组合集合即可
	result := [][]int{
		{},
	}
	path := []int{}
	var iterate func(start int) // start是指定子集的开始位置

	iterate = func(start int) {
		if start >= len(nums) {
			return
		}
		for i := start; i < len(nums); i++ {
			path = append(path, nums[i])
			// 将path放入result之中
			pathCopy := make([]int, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)

			iterate(i + 1) // 从剩余子集中继续执行相同的操作
			// 将上边找到的目标元素回退一下，继续搞下一个元素
			path = path[:len(path)-1]
		}
	}

	iterate(0)
	return result
}
